﻿namespace Graph;

//求最小生成树
//思想：贪心法，切分定理（给定任意切分，横切边的最短边，必然属于最小生成树）
public class Prim
{
    private IGraph G;
    private bool[] colors; //true：红，false：蓝，初始没有切分，顶点都是蓝色

    public MyList<Edge> ResultList { get; } = new MyList<Edge>();

    public Prim(IGraph G)
    {
        this.G = G;

        //确保联通图
        DFSConnectComponet cc = new DFSConnectComponet(G);
        if (cc.ComponentCount > 1)
        {
            return;
        }

        colors = new bool[G.V];

        colors[0] = true; //首次切分：起始点0为红（true），其余点为蓝（false）

        for (int i = 1; i < G.V; i++) //共V-1次循环，每次循环增选一条边
        {
            //查找最短的横切边
            Edge minEdge = new Edge(-1, -1, int.MaxValue);
            for (int a = 0; a < G.V; a++) //遍历所有顶点
            {
                if (colors[a]) //如果当前顶点a为红
                {
                    foreach (int b in G.Adj(a)) //遍历a的所有邻接点
                    {
                        //如果a的当前邻接点b为蓝，且横切边权值更小
                        if (!colors[b] && ((AdjDictionary)G).GetWeight(a, b) < minEdge.W)
                        {
                            //更新权值更小的横切边
                            minEdge = new Edge(a, b, ((AdjDictionary)G).GetWeight(a, b));
                        }
                    }
                }
            }

            ResultList.Add(minEdge); //找到最短的横切边，增选到最小生成树中
            //colors[minEdge.A] = true; 
            colors[minEdge.B] = true; //顶点b的颜色更新为红，有一个新的切分，再循环查找最短的横切边
        }
    }

    //验证
    static void Main(string[] args)
    {
        IGraph graph = new AdjDictionary("带权图/g.txt");

        Prim prim = new(graph);
        Console.WriteLine(prim.ResultList);
        Console.WriteLine(graph.V);
        Console.WriteLine(prim.ResultList.Count);

        Console.Read();
    }
}
